package com.huawei;

import java.util.Scanner;

/**
 * Created by Z-hong on 2024/7/4.
 */

public class HJ16_hard {

    //用于装载价格与满意度的类
    public static class Product {
        public int content;
        public int price;


        public Product(int content, int price) {
            this.content = content;
            this.price = price;
        }
    }


    //用于装载主件以及附件的类
    public static class Goods {
        public int id;
        public Product[] products;

        public Product[] remain = new Product[4];
        public int pionts;
        public int sum = 0;

        public Goods(Product[] products, int pionts, int id) {
            this.products = products;
            this.pionts = pionts;
            this.id = id;
            remain[0] = products[0];
        }


        public void add(Product product) {
            // 根据sum的不同，把各种不同的情况价格-满意度都加到remain中
            if(sum == 0){
                Product p=new Product(product.content+this.remain[0].content,product.price+this.remain[0].price);
                this.remain[1]=p;
                sum++;
            }else{
                Product p=new Product(product.content+this.remain[0].content,product.price+this.remain[0].price);
                this.remain[2]=p;
                Product p1=new Product(product.content+this.remain[1].content,product.price+this.remain[1].price);
                this.remain[3]=p1;
                sum+=2;
            }

            for (int i = 0; i < products.length; i++) {
                if (products[i] == null) {
                    products[i] = product;
                    return;
                }
                if (products[i].content > product.content) {
                    for (int j = products.length - 1; j > i; j--) {
                        products[j] = products[j - 1];
                    }
                    products[i] = product;
                }
            }
        }

    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] arr = new int[m + 1][4];
        int count = 0;
        for (int i = 1; i < m + 1; i++) {
            arr[i][0] = sc.nextInt();
            arr[i][1] = sc.nextInt();
            arr[i][2] = sc.nextInt();
            arr[i][3] = arr[i][0] * arr[i][1];
            if (arr[i][2] == 0) count++;
        }
        Goods[] goods_arr = new Goods[count + 1];
        int c = 1;
        //把主件添加到goods_arr中
        for (int i = 1; i < m + 1; i++) {
            if (arr[i][2] != 0) continue;
            Product p = new Product(arr[i][3], arr[i][0]);
            Product[] products = new Product[4];
            products[0] = p;
            Goods goods = new Goods(products, 0, i);
            goods_arr[c++] = goods;
        }

        //把附件添加到对应的主件中
        for (int i = 1; i < m + 1; i++) {
            if (arr[i][2] == 0) continue;
            Product p = new Product(arr[i][3], arr[i][0]);
            for (int j = 0; j < goods_arr.length; j++) {
                if(goods_arr[j] == null) continue;
                if (goods_arr[j].id == arr[i][2]) {
                    goods_arr[j].add(p);
                }
            }
        }

        //01背包
        int result[][] = new int[count + 1][n + 1];
        for (int i = 0; i <= n; i++) {
            result[0][i] = 0;
        }

        for (int i = 1; i <= count; i++) {
                for (int j = 1; j <= n; j++) {
                    //循环4种可能
                    for (int z = 0; z <=goods_arr[i].sum; z++) {
                        int point =goods_arr[i].remain[z].content;
                        int price = goods_arr[i].remain[z].price;

                    //判断余数是否够大
                    int remain = j - price;
                    int temp = 0;
                    // 余数够大
                    if (remain > 0 && goods_arr[i]!=null) {
                        temp = Math.max(result[i-1][j],result[i - 1][remain] + point);
                    }
                    // 当前价格最高
                    else if(price<=j){
                        temp = Math.max(result[i-1][j],point);
                    }
                    else {
                        temp = result[i - 1][j];
                    }
                    result[i][j] = Math.max(result[i][j], temp);
                }
            }

        }

        System.out.println(result[count][n]);


    }
}
